nowcoder190 G-CSL分苹果（01背包）

发表于 | 更新于: | 分类于 ， | | 阅读次数: |
字数统计: 430 | 阅读时长 ≈ 2

描述

传送门：CSL分苹果

CSL手上有n个苹果，第i个苹果的质量是wi，现在他想把这些苹果分给他的好朋友wavator和tokitsukaze。但是CSL为了不让他们打架，根据质量决定尽量地均分成两堆分给他们。现在CSL想知道到底给每个人分多少质量的苹果。

注意：苹果不能劈开来，并且如果不能正好均分，tokitsukaze小姐姐会拿到重的那一堆。

输入描述

第一行输入一个整数n(2 ≤ n ≤ 100)，第二行n个整数，表示每个苹果的质量wi(1 ≤ wi≤ 100)。

输出描述

输出两个整数，分别表示wavator和tokitsukaze得到的苹果的质量。

示例

输入

1
2
3
2 2 2

输出

1
2 4

题解

题目大意

又是友好的中文题面

思路

一道比较经典的01背包问题。
因为,它要两个人的质量差尽量小,同时苹果不能分割,所以把总质量的一半作为01背包的最大容量,然后尽可能的取最大质量。
把总质量除以二作为最大容量,每一个苹果的花费和收益都是它的重量,然后就是一个裸的01背包。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
 
int main(){
    int n;
    int a[maxn];
    int dp[maxn * maxn];
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    memset(dp,0,sizeof(dp));
    for(int i = 1; i <= n; i++){
        for(int j = sum / 2; j >= a[i]; j--){
            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
        }
    }
    cout << dp[sum / 2] << " " << sum - dp[sum / 2] << endl;
    return 0;
}